<!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="theme-color" content="#0078E7"><meta name="author" content="唐奇杭"><meta name="copyright" content="唐奇杭"><meta name="generator" content="Hexo 5.3.0"><meta name="theme" content="hexo-theme-yun"><title>二叉树的各种遍历 | 奇坑的小网站</title><link rel="stylesheet" href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@900&amp;display=swap" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/star-markdown-css@0.1.22/dist/yun/yun-markdown.min.css"><script src="//at.alicdn.com/t/font_1140697_ed8vp4atwoj.js" async></script><script src="https://cdn.jsdelivr.net/npm/scrollreveal/dist/scrollreveal.min.js" defer></script><script>document.addEventListener("DOMContentLoaded", () => {
  [".post-card",".post-content img"].forEach((target)=> {
    ScrollReveal().reveal(target);
  })
});
</script><link rel="shortcut icon" type="image/svg+xml" href="/blog/yun.svg"><link rel="mask-icon" href="/blog/yun.svg" color="#0078E7"><link rel="alternate icon" href="/yun.ico"><link rel="preload" href="/blog/css/hexo-theme-yun.css" as="style"><link rel="preload" href="/blog/js/utils.js" as="script"><link rel="preload" href="/blog/js/hexo-theme-yun.js" as="script"><link rel="prefetch" href="/blog/js/sidebar.js" as="script"><link rel="preconnect" href="https://cdn.jsdelivr.net" crossorigin><link rel="stylesheet" href="/blog/css/hexo-theme-yun.css"><script id="yun-config">
    const Yun = window.Yun || {};
    window.CONFIG = {"hostname":"tangqihang.gitee.io","root":"/blog/","title":"奇坑的小网站","version":"1.3.0","mode":"auto","copycode":true,"anonymous_image":"https://cdn.jsdelivr.net/gh/YunYouJun/cdn/img/avatar/none.jpg","say":{"api":"https://v1.hitokoto.cn","hitokoto":true},"local_search":{"path":"/blog/search.xml"},"fireworks":{"colors":["102, 167, 221","62, 131, 225","33, 78, 194"]}};
  </script><meta name="description" content="各种遍历的实现与思路">
<meta property="og:type" content="article">
<meta property="og:title" content="二叉树的各种遍历">
<meta property="og:url" content="https://tangqihang.gitee.io/blog/2021/07/22/%E7%AE%97%E6%B3%95/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%90%84%E7%A7%8D%E9%81%8D%E5%8E%86/index.html">
<meta property="og:site_name" content="奇坑的小网站">
<meta property="og:description" content="各种遍历的实现与思路">
<meta property="og:locale" content="en_US">
<meta property="article:published_time" content="2021-07-22T13:07:47.000Z">
<meta property="article:modified_time" content="2021-08-28T14:08:46.426Z">
<meta property="article:author" content="唐奇杭">
<meta property="article:tag" content="二叉树">
<meta name="twitter:card" content="summary"><script src="/blog/js/ui/mode.js"></script></head><body><script defer src="https://cdn.jsdelivr.net/npm/animejs@latest/anime.min.js"></script><script defer src="/blog/js/ui/fireworks.js"></script><canvas class="fireworks"></canvas><div class="container"><a class="sidebar-toggle hty-icon-button" id="menu-btn"><div class="hamburger hamburger--spin" type="button"><span class="hamburger-box"><span class="hamburger-inner"></span></span></div></a><div class="sidebar-toggle sidebar-overlay"></div><aside class="sidebar"><script src="/blog/js/sidebar.js"></script><ul class="sidebar-nav"><li class="sidebar-nav-item sidebar-nav-toc hty-icon-button sidebar-nav-active" data-target="post-toc-wrap" title="Table of Contents"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-list-ordered"></use></svg></li><li class="sidebar-nav-item sidebar-nav-overview hty-icon-button" data-target="site-overview-wrap" title="Overview"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-passport-line"></use></svg></li></ul><div class="sidebar-panel" id="site-overview-wrap"><div class="site-info fix-top"><a class="site-author-avatar" href="/blog/about/" title="唐奇杭"><img width="96" loading="lazy" src="/blog/22.png" alt="唐奇杭"></a><div class="site-author-name"><a href="/blog/about/">唐奇杭</a></div><a class="site-name" href="/blog/about/site.html">奇坑的小网站</a><sub class="site-subtitle">西郊有密林，助君出重围</sub><div class="site-desciption"></div></div><nav class="site-state"><a class="site-state-item hty-icon-button icon-home" href="/blog/" title="Home"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-home-4-line"></use></svg></span></a><div class="site-state-item"><a href="/blog/archives/" title="Archives"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-archive-line"></use></svg></span><span class="site-state-item-count">23</span></a></div><div class="site-state-item"><a href="/blog/categories/" title="Categories"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-folder-2-line"></use></svg></span><span class="site-state-item-count">9</span></a></div><div class="site-state-item"><a href="/blog/tags/" title="Tags"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="site-state-item-count">9</span></a></div><a class="site-state-item hty-icon-button" target="_blank" rel="noopener" href="https://yun.yunyoujun.cn" title="文档"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-settings-line"></use></svg></span></a></nav><hr style="margin-bottom:0.5rem"><div class="links-of-author"><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://github.com/summer-boythink" title="GitHub" target="_blank" style="color:#6e5494"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-github-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://music.163.com/#/user/home?id=1754803981" title="网易云音乐" target="_blank" style="color:#C20C0C"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-netease-cloud-music-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://space.bilibili.com/277650245" title="哔哩哔哩" target="_blank" style="color:#FF8EB3"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-bilibili-line"></use></svg></a></div><hr style="margin:0.5rem 1rem"><div class="links"><a class="links-item hty-icon-button" href="/blog/links/" title="我的小伙伴们" style="color:dodgerblue"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-genderless-line"></use></svg></a></div><br><a class="links-item hty-icon-button" id="toggle-mode-btn" href="javascript:;" title="Mode" style="color: #f1cb64"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-contrast-2-line"></use></svg></a></div><div class="sidebar-panel sidebar-panel-active" id="post-toc-wrap"><div class="post-toc"><div class="post-toc-content"><ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%BF%AD%E4%BB%A3%E6%96%B9%E5%BC%8F"><span class="toc-number">1.</span> <span class="toc-text">迭代方式</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%B8%AD%E5%BA%8F%EF%BC%88%E5%B7%A6-gt-%E4%B8%AD-gt-%E5%8F%B3%EF%BC%89"><span class="toc-number">1.1.</span> <span class="toc-text">中序（左-&gt;中-&gt;右）</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%80%92%E5%BD%92%E6%96%B9%E5%BC%8F"><span class="toc-number">2.</span> <span class="toc-text">递归方式</span></a></li></ol></div></div></div><div class="tag-cloud"><div class="tag-cloud-tags"><a href="/blog/tags/GO/" style="font-size: 25.5px; color: #2680d4">GO</a> <a href="/blog/tags/JS/" style="font-size: 21px; color: #4d89c0">JS</a> <a href="/blog/tags/Python/" style="font-size: 12px; color: #999">Python</a> <a href="/blog/tags/Socket/" style="font-size: 12px; color: #999">Socket</a> <a href="/blog/tags/Vue/" style="font-size: 16.5px; color: #7391ad">Vue</a> <a href="/blog/tags/Zinx/" style="font-size: 16.5px; color: #7391ad">Zinx</a> <a href="/blog/tags/node/" style="font-size: 21px; color: #4d89c0">node</a> <a href="/blog/tags/%E4%BA%8C%E5%8F%89%E6%A0%91/" style="font-size: 12px; color: #999">二叉树</a> <a href="/blog/tags/%E9%9A%8F%E7%AC%94/" style="font-size: 30px; color: #0078e7">随笔</a></div></div></aside><main class="sidebar-translate" id="content"><div id="post"><article class="post-block" itemscope itemtype="https://schema.org/Article"><link itemprop="mainEntityOfPage" href="https://tangqihang.gitee.io/blog/blog/2021/07/22/%E7%AE%97%E6%B3%95/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%90%84%E7%A7%8D%E9%81%8D%E5%8E%86/"><span hidden itemprop="author" itemscope itemtype="https://schema.org/Person"><meta itemprop="name" content="唐奇杭"><meta itemprop="description"></span><span hidden itemprop="publisher" itemscope itemtype="https://schema.org/Organization"><meta itemprop="name" content="奇坑的小网站"></span><header class="post-header"><h1 class="post-title" itemprop="name headline">二叉树的各种遍历</h1><div class="post-meta"><div class="post-time" style="display:inline-block"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-calendar-line"></use></svg></span> <time title="Created: 2021-07-22 21:07:47" itemprop="dateCreated datePublished" datetime="2021-07-22T21:07:47+08:00">2021-07-22</time><span class="post-meta-divider">-</span><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-calendar-2-line"></use></svg></span> <time title="Modified: 2021-08-28 22:08:46" itemprop="dateModified" datetime="2021-08-28T22:08:46+08:00">2021-08-28</time></div><div class="post-classify"><span class="post-category"> <span class="post-meta-item-icon" style="margin-right:3px;"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-folder-line"></use></svg></span><span itemprop="about" itemscope itemtype="https://schema.org/Thing"><a class="category" href="/blog/categories/%E7%AE%97%E6%B3%95/" style="--text-color:var(--hty-text-color)" itemprop="url" rel="index"><span itemprop="text">算法</span></a></span></span><span class="post-tag"><span class="post-meta-divider">-</span><a class="tag" href="/blog/tags/%E4%BA%8C%E5%8F%89%E6%A0%91/" style="--text-color:var(--hty-text-color)"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="tag-name">二叉树</span></a></span></div></div></header><section class="post-body" itemprop="articleBody"><div class="post-content markdown-body" style="--smc-primary:#0078E7;"><a id="more"></a>
<h3 id="迭代方式"><a href="#迭代方式" class="headerlink" title="迭代方式"></a>迭代方式</h3><h4 id="中序（左-gt-中-gt-右）"><a href="#中序（左-gt-中-gt-右）" class="headerlink" title="中序（左-&gt;中-&gt;右）"></a>中序（左-&gt;中-&gt;右）</h4><blockquote>
<p>整体思路是把左边的节点都push到stack里<br>然后再去判断它右边有没有节点，如果右边有节点，那再去找右边的左边，把右边的左边一直找到push到stack</p>
</blockquote>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">inorderTraversal</span><span class="params">(root *TreeNode)</span> []<span class="title">int</span></span> &#123;</span><br><span class="line">	res := []<span class="keyword">int</span>&#123;&#125;</span><br><span class="line">	stack := []*TreeNode&#123;&#125;</span><br><span class="line"></span><br><span class="line">  <span class="comment">//这一步为了把最左边那排元素放入stack</span></span><br><span class="line">	<span class="keyword">for</span> root != <span class="literal">nil</span> &#123;</span><br><span class="line">		stack = <span class="built_in">append</span>(stack, root)</span><br><span class="line">		root = root.Left</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">  <span class="comment">//</span></span><br><span class="line">	<span class="keyword">for</span> <span class="built_in">len</span>(stack) != <span class="number">0</span> &#123;</span><br><span class="line">		node := stack[<span class="built_in">len</span>(stack)<span class="number">-1</span>]</span><br><span class="line">		stack = stack[:<span class="built_in">len</span>(stack)<span class="number">-1</span>]</span><br><span class="line">		res = <span class="built_in">append</span>(res, node.Val)</span><br><span class="line">		node = node.Right</span><br><span class="line">		<span class="keyword">for</span> node != <span class="literal">nil</span> &#123;</span><br><span class="line">			stack = <span class="built_in">append</span>(stack, node)</span><br><span class="line">			node = node.Left</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="递归方式"><a href="#递归方式" class="headerlink" title="递归方式"></a>递归方式</h3><blockquote>
<p>使用递归来遍历树，其实是用的一套模板，这里以前序为例，并且所谓前中后，分类依据是<code>root遍历的位置</code></p>
</blockquote>
<figure class="highlight ts"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">inorderTraversal</span>(<span class="params">root: TreeNode | <span class="literal">null</span></span>): <span class="title">number</span>[] </span>&#123;</span><br><span class="line">   <span class="keyword">const</span> res = [];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">const</span> inorder = <span class="function">(<span class="params">root</span>) =&gt;</span> &#123;</span><br><span class="line">        <span class="keyword">if</span>(root == <span class="literal">null</span>) <span class="keyword">return</span>;</span><br><span class="line">		<span class="comment">//前序</span></span><br><span class="line">		res.push(root.val);</span><br><span class="line">        <span class="keyword">if</span>(root.left) inorder(root.left);</span><br><span class="line">		<span class="keyword">if</span>(root.right) inorder(root.right);</span><br><span class="line">        </span><br><span class="line">		<span class="comment">//中序</span></span><br><span class="line">        <span class="keyword">if</span>(root.left) inorder(root.left);</span><br><span class="line">		res.push(root.val);</span><br><span class="line">		<span class="keyword">if</span>(root.right) inorder(root.right);		</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//后序</span></span><br><span class="line">        <span class="keyword">if</span>(root.left) inorder(root.left);</span><br><span class="line">		<span class="keyword">if</span>(root.right) inorder(root.right);</span><br><span class="line">		res.push(root.val);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    inorder(root);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></div><div id="reward-container"><span class="hty-icon-button button-glow" id="reward-button" title="Donate" onclick="var qr = document.getElementById(&quot;qr&quot;); qr.style.display = (qr.style.display === &quot;none&quot;) ? &quot;block&quot; : &quot;none&quot;;"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-hand-coin-line"></use></svg></span><div id="reward-comment">I'm so cute. Please give me money.</div><div id="qr" style="display:none;"><div style="display:inline-block"><a target="_blank" rel="noopener" href="https://tang-webs.oss-cn-hangzhou.aliyuncs.com/tang-webs/202101012315352.jpg"><img loading="lazy" src="https://tang-webs.oss-cn-hangzhou.aliyuncs.com/tang-webs/202101012315352.jpg" alt="支付宝" title="支付宝"></a><div><span style="color:#00A3EE"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-alipay-line"></use></svg></span></div></div></div></div><ul class="post-copyright"><li class="post-copyright-author"><strong>Post author: </strong>唐奇杭</li><li class="post-copyright-link"><strong>Post link: </strong><a href="https://tangqihang.gitee.io/blog/2021/07/22/%E7%AE%97%E6%B3%95/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%90%84%E7%A7%8D%E9%81%8D%E5%8E%86/" title="二叉树的各种遍历">https://tangqihang.gitee.io/blog/2021/07/22/%E7%AE%97%E6%B3%95/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%90%84%E7%A7%8D%E9%81%8D%E5%8E%86/</a></li><li class="post-copyright-license"><strong>Copyright Notice: </strong>All articles in this blog are licensed under <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" target="_blank" rel="noopener" title="CC BY-NC-SA 4.0 "><svg class="icon"><use xlink:href="#icon-creative-commons-line"></use></svg><svg class="icon"><use xlink:href="#icon-creative-commons-by-line"></use></svg><svg class="icon"><use xlink:href="#icon-creative-commons-nc-line"></use></svg><svg class="icon"><use xlink:href="#icon-creative-commons-sa-line"></use></svg></a> unless otherwise stated.</li></ul></section></article><div class="post-nav"><div class="post-nav-item"><a class="post-nav-prev" href="/blog/2021/07/27/socket/socket%E5%A4%A7%E5%B0%8F%E7%AB%AF(%E4%B8%80)/" rel="prev" title="socket大小端(一)"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-left-s-line"></use></svg><span class="post-nav-text">socket大小端(一)</span></a></div><div class="post-nav-item"><a class="post-nav-next" href="/blog/2021/07/21/%E6%9D%82/%E5%B1%80%E5%A4%96%E4%BA%BA/" rel="next" title="局外人"><span class="post-nav-text">局外人</span><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-right-s-line"></use></svg></a></div></div></div><div id="comment"><div class="comment-tooltip text-center"><span>点击按钮跳转 GitHub Issues 评论。</span><br><span>若没有本文 Issue，您可以使用 Comment 模版新建。</span><br><a class="hty-button hty-button--raised" id="github-issues" target="_blank" rel="noopener" href="https://github.com/YunYouJun/yunyoujun.github.io/issues?q=is:issue+二叉树的各种遍历">GitHub Issues</a></div></div></main><footer class="sidebar-translate" id="footer"><div class="copyright"><span>&copy; 2019 – 2022 </span><span class="with-love" id="animate"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-cloud-line"></use></svg></span><span class="author"> 唐奇杭</span></div><div class="powered"><span>Powered by <a href="https://hexo.io" target="_blank" rel="noopener">Hexo</a> v5.3.0</span><span class="footer-separator">|</span><span>Theme - <a rel="noopener" href="https://github.com/YunYouJun/hexo-theme-yun" target="_blank"><span>Yun</span></a> v1.3.0</span></div></footer><a class="hty-icon-button" id="goUp" aria-label="back-to-top" href="#"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-up-s-line"></use></svg><svg class="progress-circle-container" viewBox="0 0 100 100"><circle class="progress-circle" id="progressCircle" cx="50" cy="50" r="48" fill="none" stroke="#0078E7" stroke-width="2" stroke-linecap="round"></circle></svg></a><a class="popup-trigger hty-icon-button icon-search" id="search" href="javascript:;" title="Search"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-search-line"></use></svg></span></a><script>window.addEventListener("DOMContentLoaded", () => {
  // Handle and trigger popup window
  document.querySelector(".popup-trigger").addEventListener("click", () => {
    document.querySelector(".popup").classList.add("show");
    setTimeout(() => {
      document.querySelector(".search-input").focus();
    }, 100);
  });

  // Monitor main search box
  const onPopupClose = () => {
    document.querySelector(".popup").classList.remove("show");
  };

  document.querySelector(".popup-btn-close").addEventListener("click", () => {
    onPopupClose();
  });

  window.addEventListener("keyup", event => {
    if (event.key === "Escape") {
      onPopupClose();
    }
  });
});
</script><script src="/blog/js/search/local-search.js" defer></script><div class="popup search-popup"><div class="search-header"><span class="popup-btn-close close-icon hty-icon-button"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-close-line"></use></svg></span></div><div class="search-input-container"><input class="search-input" id="local-search-input" type="text" placeholder="Searching..." value=""></div><div id="local-search-result"></div></div></div><script defer src="/blog/js/utils.js"></script><script defer src="/blog/js/hexo-theme-yun.js"></script></body></html>